package hard

/*
  - @author: hjz
  - @time: 2025/5/27 21:13
    4ms击败13.00%
*/
func trap(height []int) int {
	if len(height) == 0 {
		return 0
	}

	stack := make([]int, 0) // 存储柱子的索引
	water := 0

	for i := 0; i < len(height); i++ {
		// 当栈不为空且当前高度大于栈顶高度时
		for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
			top := stack[len(stack)-1]   // 取出栈顶元素
			stack = stack[:len(stack)-1] // 弹出栈顶

			if len(stack) == 0 {
				break
			}

			distance := i - stack[len(stack)-1] - 1
			boundedHeight := minT(height[i], height[stack[len(stack)-1]]) - height[top]
			water += distance * boundedHeight
		}
		stack = append(stack, i) // 将当前索引入栈
	}

	return water
}
